//
//  二叉树遍历.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/3/15.
//

import Foundation

func preOrder<T>(_ root: BinaryTreeNode<T>) {
    print(root.data)
    if let leftNode = root.leftNode {
        preOrder(leftNode)
    }
    if let rightNode = root.rightNode {
        preOrder(rightNode)
    }
}

func inOrder<T>(_ root: BinaryTreeNode<T>) {
    if let leftNode = root.leftNode {
        inOrder(leftNode)
    }
    print(root.data)
    if let rightNode = root.rightNode {
        inOrder(rightNode)
    }
}

func postOrder<T>(_ root: BinaryTreeNode<T>) {
    if let leftNode = root.leftNode {
        postOrder(leftNode)
    }
    if let rightNode = root.rightNode {
        postOrder(rightNode)
    }
    print(root.data)
}

func bfsOrder<T>(_ root: BinaryTreeNode<T>) {
    var queue = Queue<BinaryTreeNode<T>>()
    queue.enqueue(root)
    var printArr = [T]()
    while !queue.isEmpty {
        let node = queue.dequeue()!
        printArr.append(node.data)
        if let leftNode = node.leftNode {
            queue.enqueue(leftNode)
        }
        if let rightNode = node.rightNode {
            queue.enqueue(rightNode)
        }
    }
    print(printArr)
}
